package algorithm.异或;

import java.util.*;

/**
 * @ Description：一个数组中只有一组数出现了m次，其他数出现了n次，并且m<n找出出现了m次的数
 */
public class Demo2 {

    public static int[] getRandomArr(int kinds, int range, int m, int n) {
        // 数组长度
        int arrLen = m + (kinds - 1) * n;
        int[] ans = new int[arrLen];
        int mTimesNum = random(range);
        int index;
        for (index = 0; index < m; index++) {
            ans[index] = mTimesNum;
        }
        kinds--;
        Set<Integer> set = new HashSet<>();
        set.add(mTimesNum);
        while (kinds > 0) {
            int nTimesNum;
            do {
                nTimesNum = random(range);
            } while (set.contains(nTimesNum));
            set.add(nTimesNum);
            kinds--;
            for (int i = 0; i < n; i++) {
                ans[index++] = nTimesNum;
            }
        }
        return ans;
    }

    /**
     * @param range
     * @return [-range, range]
     */
    public static int random(int range) {
        return ((int) (Math.random() * range) + 1) - ((int) (Math.random() * range) + 1);
    }

    public static void main(String[] args) {
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int kinds = 4;
            int range = 100;
            int m = 2;
            int n = 5;
            int[] arr = getRandomArr(kinds, range, m, n);
            int ans = getAns1(arr, m, n);
            int ans1 = test1(arr, m, n);
            if (ans != ans1) {
                System.out.println("测试失败");
                break;
            }
        }
        System.out.println("测试结束");
//
    }

    public static int test1(int[] arr, int m, int n) {
        Map<Integer, Integer> numTimesMap = new HashMap<>();
        for (int num : arr) {
            if (numTimesMap.containsKey(num)) {
                numTimesMap.put(num, numTimesMap.get(num) + 1);
            } else {
                numTimesMap.put(num, 1);
            }
        }
        for (Integer key : numTimesMap.keySet()) {
            if (numTimesMap.get(key) == m) {
                return key;
            }
        }
        return -1;
    }

    public static int getAns1(int[] arr, int m, int n) {
        int[] bitArr = new int[32];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 32; j++) {
                if ((arr[i] & (1 << j)) != 0) {
                    bitArr[j]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < bitArr.length; i++) {
            if (bitArr[i] % n != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }

    public static int getAns(int[] arr, int m, int n) {
        int[] bitArr = new int[32];
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    bitArr[i]++;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < bitArr.length; i++) {
            if (bitArr[i] % n != 0) {
                ans |= 1 << i;
            }
//            else if (bitArr[i] % n == 0) {
//                continue;
//            } else {
//                return -1;
//            }
        }
        return ans;
    }
}
